home *** CD-ROM | disk | FTP | other *** search
/ SPACE 2 / SPACE - Library 2 - Volume 1.iso / program / 320 / compsrc2 / loop.c < prev    next >
Encoding:
C/C++ Source or Header  |  1988-10-20  |  48.1 KB  |  1,533 lines
  1. /* Move constant computations out of loops.
  2.    Copyright (C) 1987, 1988 Free Software Foundation, Inc.
  3.  
  4. This file is part of GNU CC.
  5.  
  6. GNU CC is distributed in the hope that it will be useful,
  7. but WITHOUT ANY WARRANTY.  No author or distributor
  8. accepts responsibility to anyone for the consequences of using it
  9. or for whether it serves any particular purpose or works at all,
  10. unless he says so in writing.  Refer to the GNU CC General Public
  11. License for full details.
  12.  
  13. Everyone is granted permission to copy, modify and redistribute
  14. GNU CC, but only under the conditions described in the
  15. GNU CC General Public License.   A copy of this license is
  16. supposed to have been given to you along with GNU CC so you
  17. can know your rights and responsibilities.  It should be in a
  18. file named COPYING.  Among other things, the copyright notice
  19. and this notice must be preserved on all copies.  */
  20.  
  21.  
  22. /* This is the loop optimization pass of the compiler.
  23.    It finds invariant computations within loops and moves them
  24.    to the beginning of the loop.
  25.  
  26.    It also finds cases where
  27.    a register is set within the loop by zero-extending a narrower value
  28.    and changes these to zero the entire register once before the loop
  29.    and merely copy the low part within the loop.
  30.  
  31.    Most of the complexity is in heuristics to decide when it is worth
  32.    while to do these things.  */
  33.  
  34. /* ??? verify_loop would run faster if we made one table
  35.    of the minimum and maximum luids from which each label is reached.
  36.    Also, it would be faster if loop_store_addrs were a hash table.  */
  37.  
  38. #include "config.h"
  39. #include "rtl.h"
  40. #include "insn-config.h"
  41. #include "regs.h"
  42. #include "recog.h"
  43. #include <stdio.h>
  44.  
  45. /* Vector mapping INSN_UIDs to luids.
  46.    The luids are like uids but increase monononically always.
  47.    We use them to see whether a jump comes from outside a given loop.  */
  48.  
  49. static short *uid_luid;
  50.  
  51. /* Get the luid of an insn.  */
  52.  
  53. #define INSN_LUID(INSN) (uid_luid[INSN_UID (INSN)])
  54.  
  55. /* 1 + largest uid of any insn.  */
  56.  
  57. static int max_uid;
  58.  
  59. /* 1 + luid of last insn.  */
  60.  
  61. static int max_luid;
  62.  
  63. /* Nonzero if somewhere in the current loop
  64.    there is either a subroutine call,
  65.    or a store into a memory address that is not fixed,
  66.    or a store in a BLKmode memory operand,
  67.    or too many different fixed addresses stored in
  68.    to record them all in `loop_store_addrs'.
  69.  
  70.    In any of these cases, no memory location can be regarded
  71.    as invariant.  */
  72.  
  73. static int unknown_address_altered;
  74.  
  75. /* Nonzero if somewhere in the current loop there is a store
  76.    into a memory address that is not fixed but is known to be
  77.    part of an aggregate.
  78.  
  79.    In this case, no memory reference in an aggregate may be
  80.    considered invariant.  */
  81.  
  82. static int unknown_aggregate_altered;
  83.  
  84. /* Nonzero if somewhere in the current loop there is a store
  85.    into a memory address other than a fixed address not in an aggregate.
  86.  
  87.    In this case, no memory reference in an aggregate at a varying address
  88.    may be considered invariant.  */
  89.  
  90. static int fixed_aggregate_altered;
  91.  
  92. /* Nonzero if there is a subroutine call in the current loop.
  93.    (unknown_address_altered is also nonzero in this case.)  */
  94.  
  95. static int loop_has_call;
  96.  
  97. /* Array of fixed memory addresses that are stored in this loop.
  98.    If there are too many to fit here,
  99.    we just turn on unknown_address_altered.  */
  100.  
  101. #define NUM_STORES 10
  102. static rtx loop_store_addrs[NUM_STORES];
  103. static int loop_store_widths[NUM_STORES];
  104.  
  105. /* Index of first available slot in above array.  */
  106. static int loop_store_addrs_idx;
  107.  
  108. /* During the analysis of a loop, a chain of `struct movable's
  109.    is made to record all the movable insns found.
  110.    Then the entire chain can be scanned to decide which to move.  */
  111.  
  112. struct movable
  113. {
  114.   rtx insn;            /* A movable insn */
  115.   int consec;            /* Number of consecutive following insns 
  116.                    that must be moved with this one.  */
  117.   int regno;            /* The register it sets */
  118.   short lifetime;        /* lifetime of that register;
  119.                    may be adjusted when matching movables
  120.                    that load the same value are found.  */
  121.   short times_used;        /* Number of times the register is used,
  122.                    plus uses of related insns that could
  123.                    be moved if this one is.  */
  124.   unsigned int cond : 1;    /* 1 if only conditionally movable */
  125.   unsigned int force : 1;    /* 1 means MUST move this insn */
  126.   unsigned int global : 1;    /* 1 means reg is live outside this loop */
  127.   unsigned int done : 1;    /* 1 inhibits further processing of this */
  128.   unsigned int partial : 1;    /* Moving this doesn't make it invariant.  */
  129.   struct movable *match;    /* First entry for same value */
  130.   struct movable *forces;    /* An insn that must be moved if this is */
  131.   struct movable *next;
  132. };
  133.  
  134. static FILE *loop_dump_stream;
  135.  
  136. static rtx verify_loop ();
  137. static int invariant_p ();
  138. static int consec_sets_invariant_p ();
  139. static int can_jump_into_range_p ();
  140. static void count_loop_regs_set ();
  141. static void note_addr_stored ();
  142. static int loop_reg_used_before_p ();
  143. static void constant_high_bytes ();
  144. static void scan_loop ();
  145. static rtx replace_regs ();
  146. static void move_movables ();
  147. static int may_trap_p ();
  148.  
  149. /* Entry point of this file.  Perform loop optimization
  150.    on the current function.  F is the first insn of the function
  151.    and NREGS is the number of register numbers used.  */
  152.  
  153. void
  154. loop_optimize (f, nregs, dumpfile)
  155.      /* f is the first instruction of a chain of insns for one function */
  156.      rtx f;
  157.      /* nregs is the total number of registers used in it */
  158.      int nregs;
  159.      FILE *dumpfile;
  160. {
  161.   register rtx insn;
  162.   register int i;
  163.   rtx end;
  164.   rtx last_insn;
  165.  
  166.   loop_dump_stream = dumpfile;
  167.  
  168.   init_recog ();
  169.  
  170.   /* First find the last real insn, and count the number of insns,
  171.      and assign insns their suids.  */
  172.  
  173.   for (insn = f, i = 0; insn; insn = NEXT_INSN (insn))
  174.     if (INSN_UID (insn) > i)
  175.       i = INSN_UID (insn);
  176.  
  177.   max_uid = i + 1;
  178.   uid_luid = (short *) alloca ((i + 1) * sizeof (short));
  179.   bzero (uid_luid, (i + 1) * sizeof (short));
  180.  
  181.   /* Compute the mapping from uids to luids.
  182.      LUIDs are numbers assigned to insns, like uids,
  183.      except that luids increase monotonically through the code.  */
  184.  
  185.   for (insn = f, i = 0; insn; insn = NEXT_INSN (insn))
  186.     {
  187.       last_insn = insn;
  188.       INSN_LUID (insn) = ++i;
  189.     }
  190.  
  191.   max_luid = i;
  192.  
  193.   /* Don't leave gaps in uid_luid for insns that have been
  194.      deleted.  It is possible that the first or last insn
  195.      using some register has been deleted by cross-jumping.
  196.      Make sure that uid_luid for that former insn's uid
  197.      points to the general area where that insn used to be.  */
  198.   for (i = 0; i < max_uid; i++)
  199.     {
  200.       uid_luid[0] = uid_luid[i];
  201.       if (uid_luid[0] != 0)
  202.     break;
  203.     }
  204.   for (i = 0; i < max_uid; i++)
  205.     if (uid_luid[i] == 0)
  206.       uid_luid[i] = uid_luid[i - 1];
  207.  
  208.   /* Find and process each loop.
  209.      We scan from the end, and process each loop when its start is seen,
  210.      so we process innermost loops first.  */
  211.  
  212.   for (insn = last_insn; insn; insn = PREV_INSN (insn))
  213.     if (GET_CODE (insn) == NOTE
  214.     && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
  215.       {
  216.     /* Make sure it really is a loop -- no jumps in from outside.  */
  217.     end = verify_loop (f, insn);
  218.     if (end != 0)
  219.       /* If so, optimize this loop.  */
  220.       scan_loop (insn, end, nregs);
  221.     else if (loop_dump_stream)
  222.       fprintf (loop_dump_stream,
  223.            "\nLoop at %d ignored due to multiple entry points.\n",
  224.            INSN_UID (insn));
  225.       }
  226. }
  227.  
  228. /* Optimize one loop whose start is LOOP_START and end is END.
  229.    LOOP_START is the NOTE_INSN_LOOP_BEG and END is the matching
  230.    NOTE_INSN_LOOP_END.  */
  231.  
  232. static void
  233. scan_loop (loop_start, end, nregs)
  234.      rtx loop_start, end;
  235.      int nregs;
  236. {
  237.   register int i;
  238.   register rtx p = NEXT_INSN (loop_start);
  239.   /* 1 if we are scanning insns that could be executed zero times.  */
  240.   int maybe_never = 0;
  241.   /* 1 if we are scanning insns that might never be executed
  242.      due to a subroutine call which might exit before they are reached.  */
  243.   int call_passed = 0;
  244.   /* For a rotated loop that is entered near the bottom,
  245.      this is the label at the top.  Otherwise it is zero.  */
  246.   rtx loop_top = 0;
  247.   /* This is the insn (whatever kind) before the NOTE that starts the loop.
  248.      Any insns moved out of the loop will follow it.  */
  249.   rtx before_start = PREV_INSN (loop_start);
  250.   /* Jump insn that enters the loop, or 0 if control drops in.  */
  251.   rtx loop_entry_jump = 0;
  252.   /* Place in the loop where control enters.  */
  253.   rtx scan_start;
  254.   /* Number of insns in the loop.  */
  255.   int insn_count;
  256.   int tem;
  257.   /* Indexed by register number, contains the number of times the reg
  258.      is set during the loop being scanned, or -1 if the insns that set it
  259.      have all been scanned as candidates for being moved out of the loop.
  260.      0 indicates an invariant register; -1 a conditionally invariant one.  */
  261.   short *n_times_set;
  262.   /* Indexed by register number, contains the number of times the reg
  263.      was used during the loop being scanned, not counting changes due
  264.      to moving these insns out of the loop.  */
  265.   short *n_times_used;
  266.   /* Indexed by register number, contains 1 for a register whose
  267.      assignments may not be moved out of the loop.  */
  268.   char *may_not_move;
  269.   /* Chain describing insns movable in current loop.  */
  270.   struct movable *movables = 0;
  271.   /* Last element in `movables' -- so we can add elements at the end.  */
  272.   struct movable *last_movable = 0;
  273.   /* Ratio of extra register life span we can justify
  274.      for saving an instruction.  More if loop doesn't call subroutines
  275.      since in that case saving an insn makes more difference
  276.      and more registers are available.  */
  277.   int threshold = loop_has_call ? 17 : 34;
  278.  
  279.   n_times_set = (short *) alloca (nregs * sizeof (short));
  280.   n_times_used = (short *) alloca (nregs * sizeof (short));
  281.   may_not_move = (char *) alloca (nregs);
  282.  
  283.   /* Determine whether this loop starts with a jump down
  284.      to a test at the end.  */
  285.   while (p != end
  286.      && GET_CODE (p) != CODE_LABEL && GET_CODE (p) != JUMP_INSN)
  287.     p = NEXT_INSN (p);
  288.  
  289.   /* "Loop" contains neither jumps nor labels;
  290.      it must have been a dummy.  Think no more about it.  */
  291.   if (p == end)
  292.     return;
  293.  
  294.   scan_start = p;
  295.  
  296.   /* If loop has a jump before the first label,
  297.      the true entry is the target of that jump.
  298.      Start scan from there.
  299.      But record in LOOP_TOP the place where the end-test jumps
  300.      back to so we can scan that after the end of the loop.  */
  301.   if (GET_CODE (p) == JUMP_INSN)
  302.     {
  303.       loop_entry_jump = p;
  304.       loop_top = NEXT_INSN (p);
  305.       /* Loop entry will never be a conditional jump.
  306.      If we see one, this must not be a real loop.  */
  307.       if (GET_CODE (loop_top) != BARRIER)
  308.     return;
  309.       p = JUMP_LABEL (p);
  310.       /* Check to see whether the jump actually
  311.      jumps out of the loop (meaning it's no loop).
  312.      This case can happen for things like
  313.      do {..} while (0).  */
  314.       if (p == 0
  315.       || INSN_LUID (p) < INSN_LUID (loop_start)
  316.       || INSN_LUID (p) >= INSN_LUID (end))
  317.     {
  318.       if (loop_dump_stream)
  319.         fprintf (loop_dump_stream, "\nLoop from %d to %d is phony.\n\n",
  320.              INSN_UID (loop_start), INSN_UID (end));
  321.       return;
  322.     }
  323.  
  324.       /* Find the first label after the entry-jump.  */
  325.       while (GET_CODE (loop_top) != CODE_LABEL)
  326.     {
  327.       loop_top = NEXT_INSN (loop_top);
  328.       if (loop_top == 0)
  329.         abort ();
  330.     }
  331.  
  332.       /* Maybe rearrange the loop to drop straight in
  333.      with a new test to jump around it entirely.
  334.      (The latter is considered outside the loop.)
  335.      If this is done, we no longer enter with a jump.  */
  336.       if (loop_skip_over (loop_start, end, loop_entry_jump))
  337.     loop_top = 0;
  338.       else
  339.     /* We really do enter with a jump;
  340.        scan the loop from the place where the jump jumps to.  */
  341.     scan_start = p;
  342.     }
  343.  
  344.   /* Count number of times each reg is set during this loop.
  345.      Set MAY_NOT_MOVE[I] if it is not safe to move out
  346.      the setting of register I.  */
  347.  
  348.   bzero (n_times_set, nregs * sizeof (short));
  349.   bzero (may_not_move, nregs);
  350.   count_loop_regs_set (loop_top ? loop_top : loop_start, end,
  351.                n_times_set, may_not_move, 
  352.                &insn_count, nregs);
  353.   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
  354.     may_not_move[i] = 1, n_times_set[i] = 1;
  355.   bcopy (n_times_set, n_times_used, nregs * sizeof (short));
  356.  
  357.   if (loop_dump_stream)
  358.     fprintf (loop_dump_stream, "\nLoop from %d to %d: %d real insns\n\n",
  359.          INSN_UID (loop_start), INSN_UID (end), insn_count);
  360.  
  361.   /* Scan through the loop finding insns that are safe to move.
  362.      In each such insn, store QImode as the mode, to mark it.
  363.      Then set n_times_set to -1 for the reg being set, so that
  364.      this reg will be considered invariant for subsequent insns.
  365.      We consider whether subsequent insns use the reg
  366.      in deciding whether it is worth actually moving.
  367.  
  368.      MAYBE_NEVER is nonzero if we have passed a conditional jump insn
  369.      and therefore it is possible that the insns we are scanning
  370.      would never be executed.  At such times, we must make sure
  371.      that it is safe to execute the insn once instead of zero times.
  372.      When MAYBE_NEVER is 0, all insns will be executed at least once
  373.      so that is not a problem.  */
  374.  
  375.   p = scan_start;
  376.   while (1)
  377.     {
  378.       p = NEXT_INSN (p);
  379.       /* At end of a straight-in loop, we are done.
  380.      At end of a loop entered at the bottom, scan the top.  */
  381.       if (p == scan_start)
  382.     break;
  383.       if (p == end)
  384.     {
  385.       if (loop_top != 0)
  386.         p = NEXT_INSN (loop_top);
  387.       else
  388.         break;
  389.       if (p == scan_start)
  390.         break;
  391.     }
  392.       if (GET_CODE (p) == INSN
  393.       && GET_CODE (PATTERN (p)) == SET
  394.       && GET_CODE (SET_DEST (PATTERN (p))) == REG
  395.       && ! may_not_move[REGNO (SET_DEST (PATTERN (p)))])
  396.     {
  397.       int tem1 = 0;
  398.       /* If this register is used or set outside the loop,
  399.          then we can move it only if we know this insn is
  400.          executed exactly once per iteration,
  401.          and we can check all the insns executed before it
  402.          to make sure none of them used the value that
  403.          was lying around at entry to the loop.  */
  404.       if ((uid_luid[regno_last_uid[REGNO (SET_DEST (PATTERN (p)))]] > INSN_LUID (end)
  405.            || uid_luid[regno_first_uid[REGNO (SET_DEST (PATTERN (p)))]] < INSN_LUID (loop_start))
  406.           && (maybe_never
  407.           || loop_reg_used_before_p (p, loop_start, scan_start, end)))
  408.         ;
  409.       else if ((tem = invariant_p (SET_SRC (PATTERN (p)), n_times_set))
  410.            && (n_times_set[REGNO (SET_DEST (PATTERN (p)))] == 1
  411.                || (tem1
  412.                = consec_sets_invariant_p (SET_DEST (PATTERN (p)),
  413.                               n_times_set[REGNO (SET_DEST (PATTERN (p)))],
  414.                               p, n_times_set)))
  415.            /* If the insn can cause a trap (such as divide by zero),
  416.               can't move it unless it's guaranteed to be executed
  417.               once loop is entered.  Even a function call might
  418.               prevent the trap insn from being reached
  419.               (since it might exit!)  */
  420.            && ! ((maybe_never || call_passed)
  421.              && may_trap_p (SET_SRC (PATTERN (p)))))
  422.         {
  423.           register struct movable *m;
  424.           register int regno = REGNO (SET_DEST (PATTERN (p)));
  425.           int count;
  426.           m = (struct movable *) alloca (sizeof (struct movable));
  427.           m->next = 0;
  428.           m->insn = p;
  429.           m->force = 0;
  430.           m->consec = n_times_set[REGNO (SET_DEST (PATTERN (p)))] - 1;
  431.           m->done = 0;
  432.           m->forces = 0;
  433.           m->partial = 0;
  434.           m->regno = regno;
  435.           /* Set M->cond if either invariant_p or consec_sets_invariant_p
  436.          returned 2 (only conditionally invariant).  */
  437.           m->cond = ((tem | tem1) > 1);
  438.           m->global = (uid_luid[regno_last_uid[regno]] > INSN_LUID (end)
  439.                || uid_luid[regno_first_uid[regno]] < INSN_LUID (loop_start));
  440.           m->match = 0;
  441.           m->lifetime = (uid_luid[regno_last_uid[regno]]
  442.                  - uid_luid[regno_first_uid[regno]]);
  443.           m->times_used = n_times_used[regno];
  444.           n_times_set[regno] = -1;
  445.           /* Add M to the end of the chain MOVABLES.  */
  446.           if (movables == 0)
  447.         movables = m;
  448.           else
  449.         last_movable->next = m;
  450.           last_movable = m;
  451.           /* Skip the consecutive insns, if there are any.  */
  452.           for (count = m->consec - 1; count >= 0; count--)
  453.         {
  454.           do p = NEXT_INSN (p);
  455.           while (GET_CODE (p) == NOTE);
  456.         }
  457.         }
  458.       /* If this register is always set within a STRICT_LOW_PART
  459.          or set to zero, then its high bytes are constant.
  460.          So clear them outside the loop and within the loop
  461.          just load the low bytes.
  462.          We must check that the machine has an instruction to do so.
  463.          Also, if the value loaded into the register
  464.          depends on the same register, this cannot be done.  */
  465.       else if (SET_SRC (PATTERN (p)) == const0_rtx
  466.            && GET_CODE (NEXT_INSN (p)) == INSN
  467.            && GET_CODE (PATTERN (NEXT_INSN (p))) == SET
  468.            && (GET_CODE (SET_DEST (PATTERN (NEXT_INSN (p))))
  469.                == STRICT_LOW_PART)
  470.            && (GET_CODE (XEXP (SET_DEST (PATTERN (NEXT_INSN (p))), 0))
  471.                == SUBREG)
  472.            && (SUBREG_REG (XEXP (SET_DEST (PATTERN (NEXT_INSN (p))), 0))
  473.                == SET_DEST (PATTERN (p)))
  474.            && !reg_mentioned_p (SET_DEST (PATTERN (p)),
  475.                     SET_SRC (PATTERN (NEXT_INSN (p)))))
  476.         {
  477.           register int regno = REGNO (SET_DEST (PATTERN (p)));
  478.           if (n_times_set[regno] == 2)
  479.         {
  480.           register struct movable *m;
  481.           int count;
  482.           m = (struct movable *) alloca (sizeof (struct movable));
  483.           m->next = 0;
  484.           m->insn = p;
  485.           m->force = 0;
  486.           m->consec = 0;
  487.           m->done = 0;
  488.           m->forces = 0;
  489.           m->partial = 1;
  490.           m->regno = regno;
  491.           m->cond = 0;
  492.           /* Say "global" so this register is not combined
  493.              with any other.  In fact, it is sometimes possible
  494.              to combine two of these registers, but the criteria
  495.              are special and have not been programmed in.  */
  496.           m->global = 1;
  497.           m->match = 0;
  498.           m->lifetime = (uid_luid[regno_last_uid[regno]]
  499.                  - uid_luid[regno_first_uid[regno]]);
  500.           m->times_used = n_times_used[regno];
  501.           n_times_set[regno] = -1;
  502.           /* Add M to the end of the chain MOVABLES.  */
  503.           if (movables == 0)
  504.             movables = m;
  505.           else
  506.             last_movable->next = m;
  507.           last_movable = m;
  508.           /* Skip the consecutive insns, if there are any.  */
  509.           for (count = m->consec - 1; count >= 0; count--)
  510.             {
  511.               do p = NEXT_INSN (p);
  512.               while (GET_CODE (p) == NOTE);
  513.             }
  514.         }
  515.         }
  516.     }
  517.       /* Past a call insn, we get to insns which might not be executed
  518.      because the call might exit.  This matters for insns that trap.  */
  519.       else if (GET_CODE (p) == CALL_INSN)
  520.     call_passed = 1;
  521.       /* Past a label or a jump, we get to insns for which we
  522.      can't count on whether or how many times they will be
  523.      executed during each iteration.  Therefore, we can
  524.      only move out sets of trivial variables
  525.      (those not used after the loop).  */
  526.       else if (GET_CODE (p) == CODE_LABEL || GET_CODE (p) == JUMP_INSN)
  527.     maybe_never = 1;
  528.     }
  529.  
  530.   /* For each movable insn, see if the reg that it loads
  531.      leads when it dies right into another conditionally movable insn.
  532.      If so, record that the second insn "forces" the first one,
  533.      since the second can be moved only if the first is.  */
  534.  
  535.   {
  536.     register struct movable *m, *m1;
  537.     for (m1 = movables; m1; m1 = m1->next)
  538.       {
  539.     int regno = m1->regno;
  540.     for (m = m1->next; m; m = m->next)
  541.       if (INSN_UID (m->insn) == regno_last_uid[regno])
  542.         break;
  543.     if (m != 0 && SET_SRC (PATTERN (m->insn)) == SET_DEST (PATTERN (m1->insn)))
  544.       m = 0;
  545.  
  546.     /* Increase the priority of the moving the first insn
  547.        since it permits the second to be moved as well.  */
  548.     if (m != 0)
  549.       {
  550.         m->forces = m1;
  551.         m1->lifetime += m->lifetime;
  552.         m1->times_used += m1->times_used;
  553.       }
  554.       }
  555.   }
  556.  
  557.   /* See if there are multiple movable insns that load the same value.
  558.      If there are, make all but the first point at the first one
  559.      through the `match' field, and add the priorities of them
  560.      all together as the priority of the first.  */
  561.  
  562.   {
  563.     register struct movable *m;
  564.     char *matched_regs = (char *) alloca (nregs);
  565.  
  566.     /* Regs that are used more than once are not allowed to match
  567.        or be matched.  I'm no longer sure why not.  */
  568.  
  569.     for (m = movables; m; m = m->next)
  570.       if (m->match == 0 && n_times_used[m->regno] == 1)
  571.     {
  572.       register struct movable *m1;
  573.       int regno = m->regno;
  574.  
  575.       bzero (matched_regs, nregs);
  576.       matched_regs[regno] = 1;
  577.  
  578.       for (m1 = m->next; m1; m1 = m1->next)
  579.         if (m1->match == 0 && n_times_used[m1->regno] == 1
  580.         /* A reg used outside the loop mustn't be eliminated.  */
  581.         && !m1->global
  582.         && (matched_regs[m1->regno]
  583.             ||
  584.             (
  585.              /* Can't combine regs with different modes
  586.             even if loaded from the same constant.  */
  587.              (GET_MODE (SET_DEST (PATTERN (m->insn)))
  588.               == GET_MODE (SET_DEST (PATTERN (m1->insn))))
  589.              /* See if the source of M1 says it matches M.  */
  590.              && ((GET_CODE (SET_SRC (PATTERN (m1->insn))) == REG
  591.               && matched_regs[REGNO (SET_SRC (PATTERN (m1->insn)))])
  592.              || rtx_equal_p (SET_SRC (PATTERN (m->insn)),
  593.                      SET_SRC (PATTERN (m1->insn)))
  594.              || (REG_NOTES (m->insn) && REG_NOTES (m1->insn)
  595.                  && REG_NOTE_KIND (REG_NOTES (m->insn)) == REG_EQUIV
  596.                  && REG_NOTE_KIND (REG_NOTES (m1->insn)) == REG_EQUIV
  597.                  && rtx_equal_p (XEXP (REG_NOTES (m->insn), 0),
  598.                          XEXP (REG_NOTES (m1->insn), 0)))))))
  599.           {
  600.         m->lifetime += m1->lifetime;
  601.         m->times_used += m1->times_used;
  602.         m1->match = m;
  603.         matched_regs[m1->regno] = 1;
  604.           }
  605.     }
  606.   }
  607.     
  608.   /* Now consider each movable insn to decide whether it is worth moving.  */
  609.  
  610.   move_movables (movables, n_times_set, n_times_used, threshold,
  611.          insn_count, loop_start, end, nregs);
  612. }
  613.  
  614. /* Scan MOVABLES, and move the insns that deserve to be moved.
  615.    If two matching movables are combined, replace one reg with the
  616.    other throughout.  */
  617.  
  618. static void
  619. move_movables (movables, n_times_set, n_times_used, threshold,
  620.            insn_count, loop_start, end, nregs)
  621.      struct movable *movables;
  622.      short *n_times_set;
  623.      short *n_times_used;
  624.      int threshold;
  625.      int insn_count;
  626.      rtx loop_start;
  627.      rtx end;
  628.      int nregs;
  629. {
  630.   rtx new_start = 0;
  631.   register struct movable *m;
  632.   register rtx p;
  633.   /* Map of pseudo-register replacements to handle combining
  634.      when we move several insns that load the same value
  635.      into different pseudo-registers.  */
  636.   rtx *reg_map = (rtx *) alloca (nregs * sizeof (rtx));
  637.   char *already_moved = (char *) alloca (nregs);
  638.  
  639.   bzero (already_moved, nregs);
  640.   bzero (reg_map, nregs * sizeof (rtx));
  641.  
  642.   for (m = movables; m; m = m->next)
  643.     {
  644.       /* Describe this movable insn.  */
  645.  
  646.       if (loop_dump_stream)
  647.     {
  648.       fprintf (loop_dump_stream, "Insn %d: regno %d (life %d), ",
  649.            INSN_UID (m->insn), m->regno, m->lifetime);
  650.       if (m->consec > 0)
  651.         fprintf (loop_dump_stream, "consec %d, ", m->consec);
  652.       if (m->cond)
  653.         fprintf (loop_dump_stream, "cond ");
  654.       if (m->force)
  655.         fprintf (loop_dump_stream, "force ");
  656.       if (m->global)
  657.         fprintf (loop_dump_stream, "global ");
  658.       if (m->done)
  659.         fprintf (loop_dump_stream, "done ");
  660.       if (m->match)
  661.         fprintf (loop_dump_stream, "matches %d ",
  662.              INSN_UID (m->match->insn));
  663.       if (m->forces)
  664.         fprintf (loop_dump_stream, "forces %d ",
  665.              INSN_UID (m->forces->insn));
  666.     }
  667.  
  668.       /* Ignore the insn if it's already done (it matched something else).
  669.      Otherwise, see if it is now safe to move.  */
  670.  
  671.       if (!m->done
  672.       && (! m->cond
  673.           || (1 == invariant_p (SET_SRC (PATTERN (m->insn)), n_times_set)
  674.           && (m->consec == 0
  675.               || 1 == consec_sets_invariant_p (SET_DEST (PATTERN (m->insn)),
  676.                                m->consec + 1,
  677.                                m->insn, n_times_set))))
  678.       && (! m->forces || m->forces->done))
  679.     {
  680.       register int regno;
  681.       register rtx p;
  682.       int times_used = m->times_used + m->consec;
  683.  
  684.       /* We have an insn that is safe to move.
  685.          Compute its desirability.  */
  686.  
  687.       p = m->insn;
  688.       regno = m->regno;
  689.  
  690.       if (loop_dump_stream)
  691.         fprintf (loop_dump_stream, "reg uses %d ", times_used);
  692.  
  693.       /* An insn MUST be moved if we already moved something else
  694.          which is safe only if this one is moved too: that is,
  695.          if already_moved[REGNO] is nonzero.  */
  696.  
  697.       /* An insn is desirable to move if the new lifetime of the
  698.          register is no more than THRESHOLD times the old lifetime.
  699.          If it's not desirable, it means the loop is so big
  700.          that moving won't speed things up much,
  701.          and it is liable to make register usage worse.  */
  702.  
  703.       /* It is also desirable to move if it can be moved at no
  704.          extra cost because something else was already moved.  */
  705.  
  706.       if (already_moved[regno]
  707.           || (threshold * times_used * m->lifetime) >= insn_count
  708.           || (m->forces && m->forces->done
  709.           && n_times_used[m->forces->regno] == 1))
  710.         {
  711.           int count;
  712.           register struct movable *m1;
  713.  
  714.           for (count = m->consec; count >= 0; count--)
  715.         {
  716.           rtx i1 = emit_insn_before (PATTERN (p), loop_start);
  717.           if (new_start == 0)
  718.             new_start = i1;
  719.  
  720.           if (loop_dump_stream)
  721.             fprintf (loop_dump_stream, "moved to %d", INSN_UID (i1));
  722.  
  723.           /* Mark the moved, invariant reg as being equivalent to
  724.              its constant value.  */
  725.           REG_NOTES (i1) = REG_NOTES (p);
  726.           if (REG_NOTES (i1) == 0
  727.               && ! m->partial /* But not if its a zero-extend clr. */
  728.               && ! m->global /* and not if used outside the loop
  729.                     (since it might get set outside).  */
  730.               && CONSTANT_P (SET_SRC (PATTERN (p))))
  731.             REG_NOTES (i1)
  732.               = gen_rtx (EXPR_LIST, REG_EQUIV,
  733.                  SET_SRC (PATTERN (p)), REG_NOTES (i1));
  734.           delete_insn (p);
  735.           do p = NEXT_INSN (p);
  736.           while (GET_CODE (p) == NOTE);
  737.  
  738.           /* The more insns we move, the less we like moving them.  */
  739.           threshold -= 2;
  740.         }
  741.  
  742.           /* Any other movable that loads the same register
  743.          MUST be moved.  */
  744.           already_moved[regno] = 1;
  745.  
  746.           /* The reg set here is now invariant.  */
  747.           if (! m->partial)
  748.         n_times_set[regno] = 0;
  749.  
  750.           m->done = 1;
  751.  
  752.           /* Combine with this moved insn any other matching movables.  */
  753.  
  754.           for (m1 = m->next; m1; m1 = m1->next)
  755.         if (m1->match == m)
  756.           {
  757.             /* Schedule the reg loaded by M1
  758.                for replacement so that shares the reg of M.  */
  759.             reg_map[m1->regno] = SET_DEST (PATTERN (m->insn));
  760.             /* Get rid of the matching insn
  761.                and prevent further processing of it.  */
  762.             m1->done = 1;
  763.             delete_insn (m1->insn);
  764.  
  765.             /* Any other movable that loads the same register
  766.                MUST be moved.  */
  767.             already_moved[m1->regno] = 1;
  768.  
  769.             /* The reg merged here is now invariant.  */
  770.             if (m->partial)
  771.               n_times_set[m1->regno] = 0;
  772.           }
  773.         }
  774.       else if (loop_dump_stream)
  775.         fprintf (loop_dump_stream, "not desirable");
  776.     }
  777.       else if (loop_dump_stream && !m->match)
  778.     fprintf (loop_dump_stream, "not safe");
  779.  
  780.       if (loop_dump_stream)
  781.     fprintf (loop_dump_stream, "\n");
  782.     }
  783.  
  784.   if (new_start == 0)
  785.     new_start = loop_start;
  786.  
  787.   /* Go through all the instructions in the loop, making
  788.      all the register substitutions scheduled in REG_MAP.  */
  789.   for (p = new_start; p != end; p = NEXT_INSN (p))
  790.     if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
  791.     || GET_CODE (p) == CALL_INSN)
  792.       replace_regs (PATTERN (p), reg_map);
  793. }
  794.  
  795. /* Optionally change a loop which enters just before the endtest
  796.    to one which falls straight in
  797.    after skipping around the entire loop if the endtest would drop out.
  798.    Returns 1 if the change was made, 0 if the loop was not really suitable.  */
  799.  
  800. int
  801. loop_skip_over (start, end, loop_entry_jump)
  802.      rtx start;
  803.      rtx end;
  804.      rtx loop_entry_jump;
  805. {
  806.   rtx endtestjump;
  807.   register rtx p = JUMP_LABEL (loop_entry_jump);
  808.  
  809.   while (GET_CODE (p) != INSN && GET_CODE (p) != JUMP_INSN
  810.      && GET_CODE (p) != CALL_INSN)
  811.     p = NEXT_INSN (p);
  812.   endtestjump = next_real_insn (p);
  813.  
  814.   /* Check that we (1) enter at a compare insn and (2)
  815.      the insn (presumably a jump) following that compare
  816.      is the last in the loop and jumps back to the loop beginning.  */
  817.  
  818.   if (GET_CODE (PATTERN (p)) == SET
  819.       && SET_DEST (PATTERN (p)) == cc0_rtx
  820.       && endtestjump == prev_real_insn (end)
  821.       && prev_real_insn (JUMP_LABEL (endtestjump)) == loop_entry_jump)
  822.     {
  823.       rtx newlab;
  824.       /* This is the jump that we insert.  */
  825.       rtx new_jump;
  826.  
  827.       /* Ok, duplicate that test before start of loop.  */
  828.       emit_insn_before (copy_rtx (PATTERN (p)), start);
  829.       /* Make a new entry-jump (before the original one)
  830.      whose condition is opposite to the loop-around endtest
  831.      and which jumps around the loop (to just after the endtest).  */
  832.       newlab = gen_label_rtx ();
  833.       emit_label_after (newlab, endtestjump);
  834.       emit_jump_insn_before (copy_rtx (PATTERN (endtestjump)), start);
  835.       new_jump = PREV_INSN (start);
  836.       JUMP_LABEL (new_jump) = JUMP_LABEL (endtestjump);
  837.       LABEL_NUSES (JUMP_LABEL (endtestjump))++;
  838.       invert_jump (new_jump, newlab);
  839.       /* Delete the original entry-jump.  */
  840.       delete_insn (loop_entry_jump);
  841.  
  842.       return 1;
  843.     }
  844.  
  845.   return 0;
  846. }
  847.  
  848. /* Throughout the rtx X, replace many registers according to REG_MAP.
  849.    Return the replacement for X (which may be X with altered contents).
  850.    REG_MAP[R] is the replacement for register R, or 0 for don't replace.  */
  851.  
  852. static rtx
  853. replace_regs (x, reg_map)
  854.      rtx x;
  855.      rtx *reg_map;
  856. {
  857.   register RTX_CODE code = GET_CODE (x);
  858.   register int i;
  859.   register char *fmt;
  860.  
  861.   switch (code)
  862.     {
  863.     case PC:
  864.     case CC0:
  865.     case CONST_INT:
  866.     case CONST_DOUBLE:
  867.     case CONST:
  868.     case SYMBOL_REF:
  869.     case LABEL_REF:
  870.       return x;
  871.  
  872.     case REG:
  873.       if (reg_map[REGNO (x)] != 0)
  874.     return reg_map[REGNO (x)];
  875.       return x;
  876.     }
  877.  
  878.   fmt = GET_RTX_FORMAT (code);
  879.   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
  880.     {
  881.       if (fmt[i] == 'e')
  882.     XEXP (x, i) = replace_regs (XEXP (x, i), reg_map);
  883.       if (fmt[i] == 'E')
  884.     {
  885.       register int j;
  886.       for (j = 0; j < XVECLEN (x, i); j++)
  887.         XVECEXP (x, i, j) = replace_regs (XVECEXP (x, i, j), reg_map);
  888.     }
  889.     }
  890.   return x;
  891. }
  892.  
  893. #if 0
  894. /* P is an instruction that sets a register to the result of a ZERO_EXTEND.
  895.    Replace it with an instruction to load just the low bytes
  896.    if the machine supports such an instruction,
  897.    and insert above LOOP_START an instruction to clear the register.  */
  898.  
  899. static void
  900. constant_high_bytes (p, loop_start)
  901.      rtx p, loop_start;
  902. {
  903.   register rtx new;
  904.   register int insn_code_number;
  905.  
  906.   /* Try to change (SET (REG ...) (ZERO_EXTEND (..:B ...)))
  907.      to (SET (STRICT_LOW_PART (SUBREG:B (REG...))) ...).  */
  908.  
  909.   new = gen_rtx (SET, VOIDmode,
  910.          gen_rtx (STRICT_LOW_PART, VOIDmode,
  911.               gen_rtx (SUBREG, GET_MODE (XEXP (SET_SRC (PATTERN (p)), 0)),
  912.                    SET_DEST (PATTERN (p)),
  913.                    0)),
  914.          XEXP (SET_SRC (PATTERN (p)), 0));
  915.   insn_code_number = recog (new, p);
  916.  
  917.   if (insn_code_number)
  918.     {
  919.       register int i;
  920.  
  921.       /* Clear destination register before the loop.  */
  922.       emit_insn_before (gen_rtx (SET, VOIDmode,
  923.                  SET_DEST (PATTERN (p)),
  924.                  const0_rtx),
  925.             loop_start);
  926.  
  927.       /* Inside the loop, just load the low part.  */
  928.       PATTERN (p) = new;
  929.     }
  930. }
  931. #endif
  932.  
  933. /* Verify that the ostensible loop starting at START
  934.    really is a loop: nothing jumps into it from outside.
  935.    Return the marker for the end of the loop, or zero if not a real loop.
  936.  
  937.    Also set the variables `unknown_*_altered' and `loop_has_call',
  938.    and fill in the array `loop_store_addrs'.  */
  939.  
  940. static rtx
  941. verify_loop (f, start)
  942.      rtx f, start;
  943. {
  944.   register int level = 1;
  945.   register rtx insn, end;
  946.  
  947.   /* First find the LOOP_END that matches.
  948.      Also check each insn for storing in memory and record where.  */
  949.  
  950.   unknown_address_altered = 0;
  951.   unknown_aggregate_altered = 0;
  952.   fixed_aggregate_altered = 0;
  953.   loop_has_call = 0;
  954.   loop_store_addrs_idx = 0;
  955.  
  956.   for (insn = NEXT_INSN (start); level > 0; insn = NEXT_INSN (insn))
  957.     {
  958.       if (insn == 0)
  959.     /* Parse errors can cause a loop-beg with no loop-end.  */
  960.     return 0;
  961.       if (GET_CODE (insn) == NOTE)
  962.     {
  963.       if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
  964.         ++level;
  965.       else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END)
  966.         {
  967.           --level;
  968.           if (level == 0)
  969.         {
  970.           end = insn;
  971.           break;
  972.         }
  973.         }
  974.     }
  975.       else if (GET_CODE (insn) == CALL_INSN)
  976.     {
  977.       unknown_address_altered = 1;
  978.       loop_has_call = 1;
  979.     }
  980.       else if (! unknown_address_altered)
  981.     {
  982.       if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN)
  983.         note_stores (PATTERN (insn), note_addr_stored);
  984.     }
  985.     }
  986.  
  987.   /* Now scan all jumps in the function and see if any of them can
  988.      reach a label within the range of the loop.  */
  989.  
  990.   for (insn = f; insn; insn = NEXT_INSN (insn))
  991.     if (GET_CODE (insn) == JUMP_INSN
  992.     /* Don't get fooled by jumps inserted by loop-optimize.
  993.        They don't have valid LUIDs, and they never jump into loops.  */
  994.     && INSN_UID (insn) < max_uid
  995.     && (INSN_LUID (insn) < INSN_LUID (start)
  996.         || INSN_LUID (insn) > INSN_LUID (end))
  997.     /* We have a jump that is outside the loop.
  998.        Does it jump into the loop?  */
  999.     && can_jump_into_range_p (PATTERN (insn),
  1000.                   INSN_LUID (start), INSN_LUID (end)))
  1001.       return 0;
  1002.  
  1003. #if 0      
  1004.   /* Now scan all labels between them and check for any jumps from outside.
  1005.      This uses the ref-chains set up by find_basic_blocks.
  1006.      This code is not used because it's more convenient for other reasons
  1007.      to do the loop optimization before find_basic_blocks.  */
  1008.  
  1009.   for (insn = start; insn != end; insn = NEXT_INSN (insn))
  1010.     if (GET_CODE (insn) == CODE_LABEL)
  1011.       {
  1012.     register rtx y;
  1013.     for (y = LABEL_REFS (insn); y != insn; y = LABEL_NEXTREF (y))
  1014.       if (INSN_LUID (CONTAINING_INSN (y)) < INSN_LUID (start)
  1015.           || INSN_LUID (CONTAINING_INSN (y)) > INSN_LUID (end))
  1016.         return 0;
  1017.       }
  1018. #endif
  1019.  
  1020.   return end;
  1021. }
  1022.  
  1023. /* Return 1 if somewhere in X is a LABEL_REF to a label
  1024.    located between BEG and END.  */
  1025.  
  1026. static int
  1027. can_jump_into_range_p (x, beg, end)
  1028.      rtx x;
  1029.      int beg, end;
  1030. {
  1031.   register RTX_CODE code = GET_CODE (x);
  1032.   register int i;
  1033.   register char *fmt;
  1034.  
  1035.   if (code == LABEL_REF)
  1036.     {
  1037.       register int luid = INSN_LUID (XEXP (x, 0));
  1038.       return luid > beg && luid < end;
  1039.     }
  1040.  
  1041.   fmt = GET_RTX_FORMAT (code);
  1042.   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
  1043.     {
  1044.       if (fmt[i] == 'e')
  1045.     {
  1046.       if (can_jump_into_range_p (XEXP (x, i), beg, end))
  1047.         return 1;
  1048.     }
  1049.       else if (fmt[i] == 'E')
  1050.     {
  1051.       register int j;
  1052.       for (j = 0; j < XVECLEN (x, i); j++)
  1053.         if (can_jump_into_range_p (XVECEXP (x, i, j), beg, end))
  1054.           return 1;
  1055.     }
  1056.     }
  1057.  
  1058.   return 0;
  1059. }
  1060.  
  1061. /* Record that a memory reference X is being set.  */
  1062.  
  1063. static void
  1064. note_addr_stored (x)
  1065.      rtx x;
  1066. {
  1067.   rtx addr;
  1068.   if (x == 0 || GET_CODE (x) != MEM)
  1069.     return;
  1070.   if (GET_MODE (x) == BLKmode)
  1071.     unknown_address_altered = 1;
  1072.   else if (rtx_addr_varies_p (x))
  1073.     {
  1074.       if (GET_CODE (XEXP (x, 0)) == PLUS)
  1075.     unknown_aggregate_altered = 1;
  1076.       else
  1077.     unknown_address_altered = 1;
  1078.     }
  1079.   else
  1080.     {
  1081.       register int i;
  1082.       register rtx addr = XEXP (x, 0);
  1083.  
  1084.       if (x->in_struct)
  1085.     fixed_aggregate_altered = 1;
  1086.       for (i = 0; i < loop_store_addrs_idx; i++)
  1087.     if (rtx_equal_p (loop_store_addrs[i], addr))
  1088.       {
  1089.         if (loop_store_widths[i] < GET_MODE_SIZE (GET_MODE (x)))
  1090.           loop_store_widths[i] = GET_MODE_SIZE (GET_MODE (x));
  1091.         break;
  1092.       }
  1093.       if (i == NUM_STORES)
  1094.     unknown_address_altered = 1;
  1095.       else if (i == loop_store_addrs_idx)
  1096.     {
  1097.       loop_store_widths[i] = GET_MODE_SIZE (GET_MODE (x));
  1098.       loop_store_addrs[loop_store_addrs_idx++] = addr;
  1099.     }
  1100.     }
  1101. }
  1102.  
  1103. /* Return nonzero if the rtx X is invariant over the current loop.
  1104.    N_TIMES_SET is a vector whose element I is nonzero if register I
  1105.    is set during the loop.
  1106.  
  1107.    The value is 2 if we refer to something only conditionally invariant.
  1108.  
  1109.    If `unknown_address_altered' is nonzero, no memory ref is invariant.
  1110.    Otherwise if `unknown_aggregate_altered' is nonzero,
  1111.    a memory ref is invariant if it is not part of an aggregate
  1112.    and its address is fixed and not in `loop_store_addrs'.
  1113.    Otherwise if `fixed_aggregate_altered' is nonzero,
  1114.    a memory ref is invariant
  1115.    if its address is fixed and not in `loop_store_addrs'.
  1116.    Otherwise, a memory ref is invariant if its address is fixed and not in
  1117.    `loop_store_addrs' or if it is not an aggregate.  */
  1118.  
  1119. static int
  1120. invariant_p (x, n_times_set)
  1121.      register rtx x;
  1122.      short *n_times_set;
  1123. {
  1124.   register int i;
  1125.   register RTX_CODE code = GET_CODE (x);
  1126.   register char *fmt;
  1127.   int conditional = 0;
  1128.  
  1129.   switch (code)
  1130.     {
  1131.     case CONST_INT:
  1132.     case CONST_DOUBLE:
  1133.     case SYMBOL_REF:
  1134.     case LABEL_REF:
  1135.     case CONST:
  1136.       return 1;
  1137.  
  1138.     case PC:
  1139.     case CC0:
  1140.       return 0;
  1141.  
  1142.     case REG:
  1143.       if (x == frame_pointer_rtx || x == arg_pointer_rtx
  1144.       || x->unchanging)
  1145.     return 1;
  1146.       if (n_times_set[REGNO (x)] == -1)
  1147.     return 2;
  1148.       return n_times_set[REGNO (x)] == 0;
  1149.  
  1150.     case MEM:
  1151.       /* A store in a varying-address scalar (or a subroutine call)
  1152.      could clobber anything in memory.  */
  1153.       if (unknown_address_altered)
  1154.     return 0;
  1155.       /* Don't mess with volatile memory references.  */
  1156.       if (x->volatil)
  1157.     return 0;
  1158.       /* If it's declared read-only, it is invariant
  1159.      if its address is invariant.  */
  1160.       if (x->unchanging)
  1161.     return invariant_p (XEXP (x, 0), n_times_set);
  1162.       /* A store in a varying-address aggregate component
  1163.      could clobber anything except a scalar with a fixed address.  */
  1164.       if (unknown_aggregate_altered
  1165.       && ((x->in_struct || GET_CODE (XEXP (x, 0)) == PLUS)
  1166.           || rtx_addr_varies_p (x)))
  1167.     return 0;
  1168.       /* A store in a fixed-address aggregate component
  1169.      could clobber anything whose address is not fixed,
  1170.      even an aggregate component.  */
  1171.       if (fixed_aggregate_altered
  1172.       && rtx_addr_varies_p (x))
  1173.     return 0;
  1174.       /* Any store could clobber a varying-address scalar.  */
  1175.       if (loop_store_addrs_idx
  1176.       && !(x->in_struct || GET_CODE (XEXP (x, 0)) == PLUS)
  1177.       && rtx_addr_varies_p (x))
  1178.     return 0;
  1179.       /* A store in a fixed address clobbers overlapping references.  */
  1180.       for (i = loop_store_addrs_idx - 1; i >= 0; i--)
  1181.     if (addr_overlap_p (x, loop_store_addrs[i], loop_store_widths[i]))
  1182.       return 0;
  1183.       /* It's not invalidated by a store in memory
  1184.      but we must still verify the address is invariant.  */
  1185.       break;
  1186.  
  1187.     case ASM_OPERANDS:
  1188.       /* Don't mess with insns declared volatile.  */
  1189.       if (x->volatil)
  1190.     return 0;
  1191.     }
  1192.  
  1193.   fmt = GET_RTX_FORMAT (code);
  1194.   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
  1195.     {
  1196.       if (fmt[i] == 'e')
  1197.     {
  1198.       int tem = invariant_p (XEXP (x, i), n_times_set);
  1199.       if (tem == 0)
  1200.         return 0;
  1201.       if (tem == 2)
  1202.         conditional = 1;
  1203.     }
  1204.       else if (fmt[i] == 'E')
  1205.     {
  1206.       register int j;
  1207.       for (j = 0; j < XVECLEN (x, i); j++)
  1208.         {
  1209.           int tem = invariant_p (XVECEXP (x, i, j), n_times_set);
  1210.           if (tem == 0)
  1211.         return 0;
  1212.           if (tem == 2)
  1213.         conditional = 1;
  1214.         }
  1215.  
  1216.     }
  1217.     }
  1218.  
  1219.   return 1 + conditional;
  1220. }
  1221.  
  1222. /* Return 1 if OTHER (a mem ref) overlaps the area of memory
  1223.    which is SIZE bytes starting at BASE.  */
  1224.  
  1225. int
  1226. addr_overlap_p (other, base, size)
  1227.      rtx other;
  1228.      rtx base;
  1229.      int size;
  1230. {
  1231.   int start = 0, end;
  1232.  
  1233.   if (GET_CODE (base) == CONST)
  1234.     base = XEXP (base, 0);
  1235.   if (GET_CODE (base) == PLUS
  1236.       && GET_CODE (XEXP (base, 1)) == CONST_INT)
  1237.     {
  1238.       start = INTVAL (XEXP (base, 1));
  1239.       base = XEXP (base, 0);
  1240.     }
  1241.  
  1242.   end = start + size;
  1243.   return refers_to_mem_p (other, base, start, end);
  1244. }
  1245.  
  1246. /* Return nonzero if all the insns in the loop that set REG
  1247.    are INSN and the immediately following insns,
  1248.    and if each of those insns sets REG in an invariant way
  1249.    according to TABLE (not counting uses of REG in them).
  1250.  
  1251.    The value is 2 if some of these insns are only conditionally invariant.
  1252.  
  1253.    We assume that INSN itself is the first set of REG
  1254.    and that its source is invariant.  */
  1255.  
  1256. static int
  1257. consec_sets_invariant_p (reg, n_sets, insn, table)
  1258.      int n_sets;
  1259.      rtx reg, insn;
  1260.      short *table;
  1261. {
  1262.   register rtx p = insn;
  1263.   register int regno = REGNO (reg);
  1264.   /* Number of sets we have to insist on finding after INSN.  */
  1265.   int count = n_sets - 1;
  1266.   int old = table[regno];
  1267.   int tem = 0;
  1268.  
  1269.   table[regno] = 0;
  1270.  
  1271.   while (count > 0)
  1272.     {
  1273.       register enum rtx_code code;
  1274.       p = NEXT_INSN (p);
  1275.       code = GET_CODE (p);
  1276.       if (code == INSN && GET_CODE (PATTERN (p)) == SET
  1277.       && GET_CODE (SET_DEST (PATTERN (p))) == REG
  1278.       && REGNO (SET_DEST (PATTERN (p))) == regno
  1279.       && (tem |= invariant_p (SET_SRC (PATTERN (p)), table)))
  1280.     count--;
  1281.       else if (code != NOTE)
  1282.     {
  1283.       table[regno] = old;
  1284.       return 0;
  1285.     }
  1286.     }
  1287.  
  1288.   table[regno] = old;
  1289.   /* If invariant_p ever returned 2, we return 2.  */
  1290.   return 1 + (tem & 2);
  1291. }
  1292.  
  1293. #if 0
  1294. /* I don't think this condition is sufficient to allow INSN
  1295.    to be moved, so we no longer test it.  */
  1296.  
  1297. /* Return 1 if all insns in the basic block of INSN and following INSN
  1298.    that set REG are invariant according to TABLE.  */
  1299.  
  1300. static int
  1301. all_sets_invariant_p (reg, insn, table)
  1302.      rtx reg, insn;
  1303.      short *table;
  1304. {
  1305.   register rtx p = insn;
  1306.   register int regno = REGNO (reg);
  1307.  
  1308.   while (1)
  1309.     {
  1310.       register enum rtx_code code;
  1311.       p = NEXT_INSN (p);
  1312.       code = GET_CODE (p);
  1313.       if (code == CODE_LABEL || code == JUMP_INSN)
  1314.     return 1;
  1315.       if (code == INSN && GET_CODE (PATTERN (p)) == SET
  1316.       && GET_CODE (SET_DEST (PATTERN (p))) == REG
  1317.       && REGNO (SET_DEST (PATTERN (p))) == regno)
  1318.     {
  1319.       if (!invariant_p (SET_SRC (PATTERN (p)), table))
  1320.         return 0;
  1321.     }
  1322.     }
  1323. }
  1324. #endif /* 0 */
  1325.  
  1326. /* Increment N_TIMES_SET at the index of each register
  1327.    that is modified by an insn between FROM and TO.
  1328.    If the value of an element of N_TIMES_SET becomes 2 or more,
  1329.    do not keep incrementing it; all values >= 2 would be
  1330.    equivalent anyway, and this way we avoid danger of overflow.
  1331.  
  1332.    Store in *COUNT_PTR the number of actual instruction
  1333.    in the loop.  We use this to decide what is worth moving out.  */
  1334.  
  1335. /* last_set[n] is nonzero iff reg n has been set in the current basic block.
  1336.    In that case, it is the insn that last set reg n.  */
  1337.  
  1338. static void
  1339. count_loop_regs_set (from, to, n_times_set, may_not_move, count_ptr, nregs)
  1340.      register rtx from, to;
  1341.      short *n_times_set;
  1342.      char *may_not_move;
  1343.      int *count_ptr;
  1344.      int nregs;
  1345. {
  1346.   register rtx *last_set = (rtx *) alloca (nregs * sizeof (rtx));
  1347.   register rtx insn;
  1348.   register int count = 0;
  1349.   register rtx dest;
  1350.  
  1351.   bzero (last_set, nregs * sizeof (rtx));
  1352.   for (insn = from; insn != to; insn = NEXT_INSN (insn))
  1353.     {
  1354.       if (GET_CODE (insn) == CALL_INSN)
  1355.     {
  1356.       /* If a register is used as a subroutine address,
  1357.          don't allow this register's setting to be moved out of the loop.
  1358.          This condition is not at all logically correct
  1359.          but it averts a very common lossage pattern
  1360.          and creates lossage much less often.  */
  1361.       if (GET_CODE (PATTERN (insn)) == CALL
  1362.           && GET_CODE (XEXP (PATTERN (insn), 0)) == MEM
  1363.           && GET_CODE (XEXP (XEXP (PATTERN (insn), 0), 0)) == REG)
  1364.         {
  1365.           register int regno
  1366.         = REGNO (XEXP (XEXP (PATTERN (insn), 0), 0));
  1367.           may_not_move[regno] = 1;
  1368.         }
  1369.       else if (GET_CODE (PATTERN (insn)) == SET
  1370.           && GET_CODE (SET_SRC (PATTERN (insn))) == CALL
  1371.           && GET_CODE (XEXP (SET_SRC (PATTERN (insn)), 0)) == MEM
  1372.           && GET_CODE (XEXP (XEXP (SET_SRC (PATTERN (insn)), 0), 0)) == REG)
  1373.         {
  1374.           register int regno
  1375.         = REGNO (XEXP (XEXP (SET_SRC (PATTERN (insn)), 0), 0));
  1376.           may_not_move[regno] = 1;
  1377.           /* The call insn itself sets a reg, which cannot be moved.  */
  1378.           may_not_move[REGNO (SET_DEST (PATTERN (insn)))] = 1;
  1379.           n_times_set[REGNO (SET_DEST (PATTERN (insn)))]++;
  1380.         }
  1381.     }
  1382.       if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN) 
  1383.     {
  1384.       ++count;
  1385.       if (GET_CODE (PATTERN (insn)) == CLOBBER
  1386.           && GET_CODE (XEXP (PATTERN (insn), 0)) == REG)
  1387.         /* Don't move a reg that has an explicit clobber.
  1388.            We might do so sometimes, but it's not worth the pain.  */
  1389.         may_not_move[REGNO (XEXP (PATTERN (insn), 0))] = 1;
  1390.       else if (GET_CODE (PATTERN (insn)) == SET)
  1391.         {
  1392.           dest = SET_DEST (PATTERN (insn));
  1393.           while (GET_CODE (dest) == SUBREG
  1394.              || GET_CODE (dest) == ZERO_EXTRACT
  1395.              || GET_CODE (dest) == SIGN_EXTRACT
  1396.              || GET_CODE (dest) == STRICT_LOW_PART)
  1397.         dest = XEXP (dest, 0);
  1398.           if (GET_CODE (dest) == REG)
  1399.         {
  1400.           register int regno = REGNO (dest);
  1401.           /* If this is the first setting of this reg
  1402.              in current basic block, and it was set before,
  1403.              it must be set in two basic blocks, so it cannot
  1404.              be moved out of the loop.  */
  1405.           if (n_times_set[regno] > 0 && last_set[regno] == 0)
  1406.             may_not_move[regno] = 1;
  1407.           /* If this is not first setting in current basic block,
  1408.              see if reg was used in between previous one and this.
  1409.              If so, neither one can be moved.  */
  1410.           if (last_set[regno] != 0
  1411.               && reg_used_between_p (dest, last_set[regno], insn))
  1412.             may_not_move[regno] = 1;
  1413.           ++n_times_set[regno];
  1414.           last_set[regno] = insn;
  1415.         }
  1416.         }
  1417.       else if (GET_CODE (PATTERN (insn)) == PARALLEL)
  1418.         {
  1419.           register int i;
  1420.           for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
  1421.         {
  1422.           register rtx x = XVECEXP (PATTERN (insn), 0, i);
  1423.           if (GET_CODE (x) == CLOBBER && GET_CODE (XEXP (x, 0)) == REG)
  1424.             /* Don't move a reg that has an explicit clobber.
  1425.                It's not worth the pain to try to do it correctly.  */
  1426.             may_not_move[REGNO (XEXP (x, 0))] = 1;
  1427.           if (GET_CODE (x) == SET)
  1428.             {
  1429.               dest = SET_DEST (x);
  1430.               while (GET_CODE (dest) == SUBREG
  1431.                  || GET_CODE (dest) == ZERO_EXTRACT
  1432.                  || GET_CODE (dest) == SIGN_EXTRACT
  1433.                  || GET_CODE (dest) == STRICT_LOW_PART)
  1434.             dest = XEXP (dest, 0);
  1435.               if (GET_CODE (dest) == REG)
  1436.             {
  1437.               register int regno = REGNO (dest);
  1438.               ++n_times_set[regno];
  1439.               may_not_move[regno] = 1;
  1440.               last_set[regno] = insn;
  1441.             }
  1442.             }
  1443.         }
  1444.         }
  1445.     }
  1446.       if (GET_CODE (insn) == CODE_LABEL || GET_CODE (insn) == JUMP_INSN)
  1447.     bzero (last_set, nregs * sizeof (rtx));
  1448.     }
  1449.   *count_ptr = count;
  1450. }
  1451.  
  1452. /* Given a loop that is bounded by LOOP_START and LOOP_END
  1453.    and that is entered at SCAN_START,
  1454.    return 1 if the register set by insn INSN is used by
  1455.    any insn that precedes INSN in cyclic order starting
  1456.    from the loop entry point.  */
  1457.  
  1458. static int
  1459. loop_reg_used_before_p (insn, loop_start, scan_start, loop_end)
  1460.      rtx insn, loop_start, scan_start, loop_end;
  1461. {
  1462.   rtx reg = SET_DEST (PATTERN (insn));
  1463.   if (INSN_LUID (scan_start) > INSN_LUID (insn))
  1464.     return (reg_used_between_p (reg, scan_start, loop_end)
  1465.         || reg_used_between_p (reg, loop_start, insn));
  1466.   else
  1467.     return reg_used_between_p (reg, scan_start, insn);
  1468. }
  1469.  
  1470. /* Return nonzero if evaluating rtx X might cause a trap.  */
  1471.  
  1472. static int
  1473. may_trap_p (x)
  1474.      rtx x;
  1475. {
  1476.   int i;
  1477.   enum rtx_code code = GET_CODE (x);
  1478.   char *fmt;
  1479.  
  1480.   switch (code)
  1481.     {
  1482.       /* Handle these cases fast.  */
  1483.     case CONST_INT:
  1484.     case CONST_DOUBLE:
  1485.     case SYMBOL_REF:
  1486.     case LABEL_REF:
  1487.     case CONST:
  1488.     case PC:
  1489.     case CC0:
  1490.     case REG:
  1491.       return 0;
  1492.  
  1493.       /* Division by a non-constant might trap.  */
  1494.     case DIV:
  1495.     case MOD:
  1496.     case UDIV:
  1497.     case UMOD:
  1498.       if (! CONSTANT_P (XEXP (x, 1))
  1499.       && GET_CODE (XEXP (x, 1)) != CONST_DOUBLE)
  1500.     return 1;
  1501.       break;
  1502.  
  1503.       /* Memory ref can trap unless it's a static var or a stack slot.  */
  1504.     case MEM:
  1505.       return rtx_varies_p (XEXP (x, 0));
  1506.  
  1507.     case SET:
  1508.       /* Any floating arithmetic may trap.  */
  1509.       if (GET_MODE_CLASS (GET_MODE (SET_DEST (x))) == MODE_FLOAT
  1510.       && GET_CODE (SET_SRC (x)) != REG
  1511.       && GET_CODE (SET_SRC (x)) != MEM)
  1512.     return 1;
  1513.     }
  1514.  
  1515.   fmt = GET_RTX_FORMAT (code);
  1516.   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
  1517.     {
  1518.       if (fmt[i] == 'e')
  1519.     {
  1520.       if (may_trap_p (XEXP (x, i)))
  1521.         return 1;
  1522.     }
  1523.       else if (fmt[i] == 'E')
  1524.     {
  1525.       register int j;
  1526.       for (j = 0; j < XVECLEN (x, i); j++)
  1527.         if (may_trap_p (XVECEXP (x, i, j)))
  1528.           return 1;
  1529.     }
  1530.     }
  1531.   return 0;
  1532. }
  1533.